#include "IterativeDFSMultipleCycleFinderAlgorithm.h"

#include <stack>

#include "FileType.h"

using namespace analyzer;

IterativeDFSMultipleCycleFinderAlgorithm::IterativeDFSMultipleCycleFinderAlgorithm(void)
{
	failOnFirst = false;
}


IterativeDFSMultipleCycleFinderAlgorithm::~IterativeDFSMultipleCycleFinderAlgorithm(void)
{
	// empty destructor
}

std::vector<std::vector<int> > IterativeDFSMultipleCycleFinderAlgorithm::findCycle(const Graph& graph) {

	std::vector<VertexColor> color(boost::num_vertices(graph), white);	

	std::stack<Vertex> vertexStack;
	bool childrenVisited;

	std::map<Vertex, Vertex> parentVertexMap;
	Vertex u;

	boost::graph_traits<Graph>::vertex_iterator vi, vi_end;
	boost::graph_traits<Graph>::adjacency_iterator ui, ui_end;

	std::vector<std::vector<int> > cyclicVertices;

	bool stopSearch = false;

	boost::property_map<Graph, vertex_type_t>::type vertexTypes = boost::get(vertex_type_t(), const_cast<Graph&>(graph));

	for (boost::tie(vi, vi_end) = vertices(graph); vi != vi_end && !stopSearch; ++vi) {

		if (boost::get(vertexTypes, *vi) == SOURCE_FILE && color[*vi] == white) {
			vertexStack.push(*vi);

			while(vertexStack.size() > 0 && !stopSearch) {

				u = vertexStack.top();

				color[u] = gray;

				childrenVisited = true;
				for (boost::tie(ui, ui_end) = adjacent_vertices(u, graph); ui != ui_end && !stopSearch; ++ui) {

					if (color[*ui] == white) {
						childrenVisited = false;

						vertexStack.push(*ui);
						parentVertexMap.insert(std::pair<Vertex, Vertex>(*ui, u));

					} else if (color[*ui] == gray) {
						
						// TODO find the better way to exit those loops
						stopSearch = failOnFirst;

						cyclicVertices.push_back(getCyclicVertices(*ui, u, parentVertexMap));
					}
				}

				if(childrenVisited) {
					color[u] = black;
					vertexStack.pop();
				}
			}
		}
	}	

	return cyclicVertices;
}

std::vector<int> IterativeDFSMultipleCycleFinderAlgorithm::getCyclicVertices(Vertex searchVertex, Vertex startVertex, std::map<Vertex, Vertex> parentVertexMap) {

	std::vector<int> result;
	Vertex u = startVertex;

	result.push_back(searchVertex);

	do {
		result.push_back(u);
	} while((u = parentVertexMap[u]) != searchVertex && u != result.back());

	result.push_back(searchVertex);

	return result;
}

bool IterativeDFSMultipleCycleFinderAlgorithm::getFailOnFirst() const {

	return failOnFirst;
}

void IterativeDFSMultipleCycleFinderAlgorithm::setFailOnFirst(bool failOnFirst) {

	this -> failOnFirst = failOnFirst;
}
